//
//  Problem131.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/23.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 131. 分割回文串 【动态规划】【回文】【分割子串】
 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
 返回 s 所有可能的分割方案。

 示例:
 输入: "aab"
 输出:
 [
   ["aa","b"],
   ["a","a","b"]
 ]
 */
@objcMembers class Problem131: NSObject {
    func solution() {
        let str = "aab"
        print(partition("aababa"))
        
//        print(isRecol("124sdfsw"))
//        print(isRecol("124421"))
    }
    
    /*
     动态规划
     1: 创建一个dp[key: [[]]]
     2: dp[str] = [[]]: str包含的回文数组
     3: str = "aab"
        dp[i] = str(0~i)是回文 * dp[i~end]
     */
    func partition(_ s: String) -> [[String]] {
        if s.count == 0 {
            return []
        } else if s.count == 1 {
            return [[s]]
        } else if s.count == 2 {
            if s.first == s.last! {
                return [[String(s.first!), String(s.last!)], [s]]
            } else {
                return [[String(s.first!), String(s.last!)]]
            }
        }
        
        var dp:[String: [[String]]] = [:]
        return partitionSub(s, s.startIndex, &dp)
    }
    
    func partitionSub(_ s: String, _ i: String.Index, _ dp: inout [String: [[String]]]) -> [[String]] {
        if i == s.endIndex {
            return []
        }
        let lstr = s[i..<s.endIndex]
        
        if let safeStrs = dp[String(lstr)]  {
            return safeStrs
        }
        
        
        var si = s.index(i, offsetBy: 1)
        var result: [[String]] = []
        while si < s.endIndex {
            let fstr = s[i..<si]
            
            if isRecol(String(fstr)) == true {
                let lastArrays = partitionSub(s, si, &dp)
                
                if lastArrays.count == 0 {
                    result.append([String(fstr)])
                } else {
                    for array in lastArrays {
                        var subarray:[String] = [String(fstr)]
                        subarray.append(contentsOf: array)
                        result.append(subarray)
                    }
                }
            }
            
            si = s.index(si, offsetBy: 1)
        }
        
        let fstr = s[i..<si]
        if isRecol(String(fstr)) == true {
            result.append([String(fstr)])
        }
        
        
        return result
    }
    
    func isRecol(_ str: String) -> Bool {
        if str.count == 0 {
            return false
        } else if str.count == 1 {
            return true
        }
        
        for i in 0..<str.count/2 {
            let fstr = str[str.index(str.startIndex, offsetBy: i)..<str.index(str.startIndex, offsetBy: i+1)]
            let lstr = str[str.index(str.endIndex, offsetBy: -i-1)..<str.index(str.endIndex, offsetBy: -i)]
            if fstr != lstr {
                return false
            }
        }
        return true
    }
}
